class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if (root == NULL) return true;
        return isBalanced(root->left) && isBalanced(root->right) && abs(dep[root->left]-depth[root->right])<=1; 
    }
    int abs(int a) { return a>0? a:-a;}
    int max(int a, int b) { return a>b? a: b;}
    void depth(TreeNode *root) {
        if (root == NULL) return 0;
        dep[root] = max(depth(root->left), depth(root->right)) + 1;
        return dep[root];
    }
    map<const TreeNode*, int, cmp> dep;
    struct cmp {
        bool operator() (const TreeNode* t1, const TreeNode* t2) const {
            return (t1 == t2);
        }
    }
};
